package com.lun.swordtowardoffer2.c13;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum2 {

	public List<List<Integer>> combinationSum2(int[] nums, int target){
		List<Integer> path = new ArrayList<>();
		List<List<Integer>> result =  new ArrayList<>();
		Arrays.sort(nums);
		backtracking(nums, 0, target, 0, path, result);
		return result;
	}

	private void backtracking(int[] nums, int startIndex, int target, int sum,// 
			List<Integer> path, List<List<Integer>> result) {
		
		if(target == sum) {				
			result.add(new ArrayList<>(path));
			return;
		}
		
		for(int i = startIndex; i < nums.length && // 
				target >= sum + nums[i]; //由于排序的缘故，累加超过target后，同层的也没必要继续下去
				i = getNext(nums, i)) {

			path.add(nums[i]);
			backtracking(nums, i + 1, target, sum + nums[i], path, result);
			path.remove(path.size() - 1);
		}
		
	}
	
	/**
	 * 带去重作用
	 */
	private int getNext(int[] nums, int index) {
		int next = index;
		do {			
			next++;
		}while(next < nums.length && nums[index] == nums[next]);
		return next;
	}
	
}
